Masala #0748

Xotira 16 MB Vaqt 2500 ms Qiyinchiligi 65 %

Prefiks funksiya

Dasturlash musobaqasi bilan shug’ullanib yurgan barchaga Prefiks funksiya nima ekanligi ma’lum bo’lsa kerak. Agar bilmasangiz Prefiks funksiya haqida https://e-maxx.ru/algo/prefix_function havoladan o’rganib olishingiz mumkin.

Keling endi asosiy masalaga o’tamiz!

\(S\) to’plam \(m\) ta harfli alifbodan tuzilgan uzunligi \(n\) ga teng bo’lgan barcha satrlar to’plami.

\(F(s)\) funksiyasi \(\text{prefix\_function}(s)\) dan olingan to’plamning eng katta qiymati bo’lsin.

Sizning vazifangiz \(\sum_{s∈S}F(s)\) ni \(X\) ga bo’lgandagi qoldiqni hisoblashdan iborat.

Kiruvchi ma'lumotlar:

Kirish faylining yagona satrida uchta butun son, \(n (1 \le n \le 22)\), \(m (1 \le m \le 10^9)\) va \(X (1 \le X \le 10^9)\) sonlari kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida yagona butun son, \(\sum_{s∈S}F(s)\) ni \(X\) ga bo’lgandagi qoldiqni chop eting!

Misollar

#	input.txt	output.txt
1	3 2 1000	8

Izoh:

F(aaa) = 2
F(aab) = 1
F(aba) = 1
F(abb) = 0
F(baa) = 0
F(bab) = 1
F(bba) = 1
F(bbb) = 2

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin